// poj3709
// 题意：给定n(<=500000)个数，从小到大排序，现在要使得对于每个数都有
//       至少k个数和它相等，可以的操作是减小某个数，费用就是减小的量。
//       求要使这n个数满足要求，最小的费用。
//
// 题解：延迟更新的斜率优化。
//       首先一般的dp是dp[i] = min{ dp[j] + (sum[i] - sum[j] - da[j + 1] * (i - j))}
//       （dp[i]表示前i个数满足要求的最小费用。）
//       复杂度不够，考虑斜率优化，
//       推出 Yi = dp[i] - sum[i] + da[i+1]*i
//            Xi = da[i+1]
//       优化不等式是，对于k<j<i
//           (Yj - Yk) / (Xj - Xk) <= i，
//       i单调增，维护下凸壳。
//       现在这题解决个大概，还有k个的限制。也就是说考虑dp方程，i的转移过来
//       j至少和它距离有k，才能保证每段数都至少有k个。
//
//       那么我们只需要延迟更新就好。当前做到第i个状态，当到状态i+k的时候
//       再去更新它。
//
// 统计：1110ms, 1h, 1a
//
// run: $exec < input
#include <cstdio>

long long const inf = (long long)(1) << 60;
int const maxn = 500100;
int q[4 * maxn];
long long da[maxn], sum[maxn];
long long dp[maxn];
int n, k;

long long coord_y(int i) { return dp[i] - sum[i] + da[i + 1] * i; }
long long coord_x(int i) { return da[i + 1]; }
long long slope_y(int i, int j) { return coord_y(i) - coord_y(j); }
long long slope_x(int i, int j) { return coord_x(i) - coord_x(j); }

bool slope_less(int i, int j, int k)
{
	return slope_y(i, j) * slope_x(j, k) <= slope_y(j, k) * slope_x(i, j);
}

int main()
{
	int T; std::scanf("%d", &T);
	while (T--) {
		std::scanf("%d %d", &n, &k);
		for (int i = 1; i <= n; i++) std::scanf("%lld", &da[i]), sum[i] = sum[i - 1] + da[i];
		for (int i = 1; i < k; i++) dp[i] = inf;
		int head = 1, tail = 1;
		for (int i = k; i <= n; i++) {
			if (dp[i - k] < inf) {
				while (head < tail && slope_less(i - k, q[tail], q[tail - 1]))
					tail--;
				q[++tail] = i - k;
			}
			while (head < tail && slope_y(q[head + 1], q[head]) <= i * slope_x(q[head + 1], q[head]))
				head++;
			int j = q[head];
			dp[i] = dp[j] + (sum[i] - sum[j]) - da[j + 1] * (i - j);
//			std::printf("dp[%d] = %lld\n", i, dp[i]);
		}
		std::printf("%lld\n", dp[n]);
	}
}

